迭代器失效

当使用一个容器的insert或者erase函数通过迭代器插入或删除元素可能会导致迭代器失效，因此很多建议都是让我们获取insert或者erase返回的迭代器，以便用重新获取新的有效的迭代器进行正确的操作。

1
2
iter = vec.insert(iter);
iter = vec.erase(iter);

迭代器失效的原因

以vector为例，当我们插入一个元素时它的预分配空间不够时，它会重新分配一段新空间，将原空间上的元素复制到新空间上，然后再把新加入的元素放到新空间的尾部，以满足vector元素要求连续存储的目的。而后原空间会被系统撤销或者征作他用，于是指向原空间的迭代器类似于“悬垂指针”一样的东西，指向了一片非法区域。

迭代器失效分类

  • vector

    • vector的push_back操作可能没事，但是一旦引发内存重分配，所有迭代器都会失效
    • vector的insert操作插入点之后的所有迭代器失效，但一旦发生内存重分配，所有迭代器都会失效
    • vector的erase操作插入点之后的所有迭代器失效
    • vector的reserve操作所有迭代器失效（导致内存重分配）

  • list/map

    插入不会使得任何迭代器失效，删除运算使指向删除位置的迭代器失效，但是不会失效其他迭代器

  • deque

    • insert操作会使所有迭代器失效
    • erase操作会使所有迭代器失效

  • 对于关联容器（map、set、multimap、multiset），删除当前的iterator，仅仅会使当前的iterator失效，只要在erase时，递增当前iterator即可。这是因为map之类的容器使用了红黑树来实现，插入、删除一个结点不会对其他结点产生影响。erase迭代器只是被删元素的迭代器失效，但是因为erase()函数返回为void类型，所以要采用erase(iter++)的方式删除迭代器：

    1
    2
    3
    4
    5
    6
    7
    8
    for (iter = cont.begin(); it != cont.end();)
    {
       (*iter)->doSomething();
       if (shouldDelete(*iter))
          cont.erase(iter++);
       else
          ++iter;
    }

  • 对于序列式容器（vector、deque），删除当前的iterator会使后面所有元素的iterator失效，这是因为vector、deque使用了连续分配的内存，删除一个元素会导致后面所有元素向前移动一个位置，所以不能使用erase(iter++)的方式，不过erase()方法返回了下一个有效的iterator

    1
    2
    3
    4
    5
    6
    7
    8
    for (iter = cont.begin(); iter != cont.end();)
    {
       (*it)->doSomething();
       if (shouldDelete(*iter))
          iter = cont.erase(iter); 
       else
          ++iter;
    }

  • 对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的iterator，因此上面两种方法都可以使用。

说明

本文转载自文章 失效迭代器（Invalidating Iterators）。